#pragma once
#pragma pack(push, 1)

#include "wchar.h"

struct TreeNode
{
	enum {Red, Black};
	
	int key;
	int data;
	char color; // used in red-black tree
	
	TreeNode* leftChild;
	TreeNode* rightChild;
	TreeNode* parent;
	
	TreeNode() : key(-1), data(0), color(Red), leftChild(0), rightChild(0), parent(0) {}
	~TreeNode()
	{
		if (leftChild) { delete leftChild; }
		if (rightChild) { delete rightChild; }
	}
};

extern TreeNode* g_root;

// Binary search tree
extern void		bst_insert(int key, int data);
extern int		bst_query(int key);
extern void		bst_delete(int key);

// red-black tree
extern void		rb_insert(int key, int data);
extern int		rb_query(int key);
extern void		rb_delete(int key);